{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #memoization #array #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #记忆化搜索 #数组 #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordBreak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词拆分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个字符串列表 <code>wordDict</code> 作为字典。请你判断是否可以利用字典中出现的单词拼接出 <code>s</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"leetcode\", wordDict = [\"leet\", \"code\"]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 返回 true 因为 \"leetcode\" 可以由 \"leet\" 和 \"code\" 拼接成。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 返回 true 因为 <code>\"</code>applepenapple<code>\"</code> 可以由 <code>\"</code>apple\" \"pen\" \"apple<code>\" 拼接成</code>。\n",
    "&nbsp;    注意，你可以重复使用字典中的单词。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= wordDict.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= wordDict[i].length &lt;= 20</code></li>\n",
    "\t<li><code>s</code> 和 <code>wordDict[i]</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>wordDict</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-break](https://leetcode.cn/problems/word-break/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-break](https://leetcode.cn/problems/word-break/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leetcode\"\\n[\"leet\",\"code\"]', '\"applepenapple\"\\n[\"apple\",\"pen\"]', '\"catsandog\"\\n[\"cats\",\"dog\",\"sand\",\"and\",\"cat\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        word_set = set(wordDict)\n",
    "        dp = [True] + [False] * len(s)\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(i):\n",
    "                if dp[j] and s[j:i] in word_set:\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "        if not dp[len(s)]:\n",
    "            return []\n",
    "        \n",
    "        word_set = set(wordDict)\n",
    "        poss_dict = collections.defaultdict(list)\n",
    "        poss_dict[0] = [\"\"]\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(i):\n",
    "                if len(poss_dict[j]) > 0 and s[j:i] in word_set:\n",
    "                    for p in poss_dict[j]:\n",
    "                        temp = s[j:i] if p == \"\" else p + \" \" + s[j:i]\n",
    "                        poss_dict[i].append(temp)\n",
    "        return poss_dict[len(s)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'List[str]':\n",
    "        def kmp(pattern, text):\n",
    "            np, nt = len(pattern), len(text)\n",
    "            q = [-1] * np\n",
    "            i, j = -1, 1\n",
    "            while j < np:\n",
    "                if pattern[j] == pattern[i + 1]:\n",
    "                    q[j] = i + 1\n",
    "                    i, j = i + 1, j + 1\n",
    "                elif i == -1:\n",
    "                    q[j] = -1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i = q[i]\n",
    "\n",
    "            ret = []\n",
    "            i, j = -1, -1\n",
    "            while j < nt - 1:\n",
    "                if text[j + 1] == pattern[i + 1]:\n",
    "                    i, j = i + 1, j + 1\n",
    "                    if i == np - 1:\n",
    "                        ret.append(j - i)\n",
    "                        i = q[i]\n",
    "                elif i == -1:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i = q[i]\n",
    "\n",
    "            return ret\n",
    "\n",
    "        ns = len(s)\n",
    "        h = [set() for i in range(ns)]\n",
    "        for word_idx, word in enumerate(wordDict):\n",
    "            indices = kmp(word, s)\n",
    "            for idx in indices:\n",
    "                h[idx].add(word_idx)\n",
    "        # print(h)\n",
    "\n",
    "        # first pass, just try if there is solution\n",
    "        dp = [False for i in range(ns)]\n",
    "        for i in range(ns - 1, -1, -1):\n",
    "            for word_idx in h[i]:\n",
    "                word = wordDict[word_idx]\n",
    "                if i + len(word) == ns:\n",
    "                    dp[i] = True\n",
    "                else:\n",
    "                    dp[i] |= dp[i + len(word)]\n",
    "\n",
    "        if not dp[0]:\n",
    "            return []\n",
    "\n",
    "        dp = [[] for i in range(ns)]\n",
    "        for i in range(ns - 1, -1, -1):\n",
    "            for word_idx in h[i]:\n",
    "                word = wordDict[word_idx]\n",
    "                if i + len(word) == ns:\n",
    "                    dp[i].append([word_idx])\n",
    "                else:\n",
    "                    for seq in dp[i + len(word)]:\n",
    "                        dp[i].append([word_idx] + seq)\n",
    "        ret = []\n",
    "        for seq in dp[0]:\n",
    "            ret.append(' '.join(map(wordDict.__getitem__, seq)))\n",
    "        # print(ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'List[str]':\n",
    "        def helper(words, s, memo):\n",
    "            if s not in memo:\n",
    "                memo[s]=[]\n",
    "                for w in words:\n",
    "                    if s.startswith(w):\n",
    "                        if s==w:\n",
    "                            memo[s].append(w)\n",
    "                        else:\n",
    "                            for r in helper(words,s[len(w):],memo):\n",
    "                                memo[s].append(w + ' ' + r)\n",
    "            return memo[s]\n",
    "        return helper(wordDict,s,{})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        memo = {len(s): ['']}\n",
    "        def sentences(i):\n",
    "            if i not in memo:\n",
    "                memo[i] = [s[i:j] + (tail and ' ' + tail)\n",
    "                           for j in range(i+1, len(s)+1)\n",
    "                           if s[i:j] in wordDict\n",
    "                           for tail in sentences(j)]\n",
    "            return memo[i]\n",
    "        return sentences(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        if not wordDict:\n",
    "            return []\n",
    "        ml = max(len(word) for word in wordDict)\n",
    "        ls = len(s)\n",
    "        wbstate = [False] * (ls + 1)\n",
    "        wbstate[0] = True\n",
    "        for i in range(1, ls + 1):\n",
    "            for j in range(max(0, i - ml), i):\n",
    "                if wbstate[j] and s[j:i] in wordDict:\n",
    "                    wbstate[i] = True\n",
    "        if not wbstate[ls]:\n",
    "            return []\n",
    "        else:\n",
    "            return self.wb2st(s, wordDict, wbstate)\n",
    "\n",
    "    def wb2st(self, s:str, wordDict: List[str], wbstate: List[bool]) -> List[str]:\n",
    "        ls = len(s)\n",
    "        if ls == 0:\n",
    "            return [\"\"]\n",
    "        stlist = []\n",
    "        #pdb.set_trace()\n",
    "        for i in range(ls - 1, -1, -1):\n",
    "            if wbstate[i] and s[i:ls] in wordDict:\n",
    "                if i == 0:\n",
    "                    stlist.append(s[i:ls])\n",
    "                else:\n",
    "                    templist = self.wb2st(s[0:i], wordDict, wbstate[0:i + 1])\n",
    "                    for tmp in templist:\n",
    "                        stlist.append(tmp + \" \" + s[i:ls])\n",
    "        return stlist\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        len_s = len(s)\n",
    "        reachable = [[None] * len_s for _ in range(len_s)]\n",
    "        for word in wordDict:\n",
    "            for i in range(0, len_s - len(word) + 1):\n",
    "                if s[i:i + len(word)] == word:\n",
    "                    reachable[i + len(word) - 1][i] = {word}\n",
    "\n",
    "        for i in range(1, len_s - 1):\n",
    "            if not any(reachable[i]):\n",
    "                for j in range(len_s):\n",
    "                    reachable[j][i + 1] = None\n",
    "\n",
    "        if not any(reachable[-1]):\n",
    "            return []\n",
    "\n",
    "        def set_product(row, r):\n",
    "            word = r.pop()\n",
    "            res = set()\n",
    "            for s_ in row:\n",
    "                if s_:\n",
    "                    res.update({s__ + \" \" + word for s__ in s_ if s__})\n",
    "            return res or None\n",
    "\n",
    "        for i in range(1, len_s):\n",
    "            for j in range(1, len_s):\n",
    "                if reachable[i][j]:\n",
    "                    reachable[i][j] = set_product(reachable[j - 1], reachable[i][j])\n",
    "\n",
    "        res = set()\n",
    "        for r_ in reachable[-1]:\n",
    "            res = res.union(r_) if r_ else res\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        memo={}\n",
    "        dic=set(wordDict)\n",
    "        def helper(s,dic):\n",
    "            if s in memo:\n",
    "                return memo[s]\n",
    "            res=[]\n",
    "            if s in dic:\n",
    "                res.append(s)\n",
    "            n=len(s)\n",
    "            for i in range(n-1):\n",
    "                temp=s[:i+1]\n",
    "                if temp in dic:\n",
    "                    last=helper(s[i+1:],dic)\n",
    "                    if last:\n",
    "                        for item in last:\n",
    "                            res.append(temp+' '+item)\n",
    "            memo[s]=res\n",
    "            return res\n",
    "        return helper(s,dic)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        dp=[0]*len(s)\n",
    "        for i in wordDict:\n",
    "            if s[:len(i)]==i:\n",
    "                dp[len(i)-1]=1\n",
    "        for i in range(1,len(s)):\n",
    "            if dp[i-1]==1:\n",
    "                for j in wordDict:\n",
    "                    if s[i:i+len(j)]==j:\n",
    "                        dp[i+len(j)-1]=1\n",
    "                        print(s[i:i+len(j)],'  ',j)\n",
    "        \n",
    "        result=[]\n",
    "        tmp=[]\n",
    "\n",
    "            \n",
    "                \n",
    "        print(dp)\n",
    "        \n",
    "        def dfs(s,result,index,tmp):\n",
    "            if index==len(s):\n",
    "                result.append(' '.join(tmp))\n",
    "                return\n",
    "            for i in range(index,len(s)):\n",
    "                if s[index:i+1] in wordDict:\n",
    "                    tmp.append(s[index:i+1])\n",
    "                    dfs(s,result,i+1,tmp)\n",
    "                    tmp.pop(len(tmp)-1)\n",
    "                    \n",
    "                    \n",
    "        if dp[len(s)- 1]==1:\n",
    "            dfs(s,result,0,tmp)\n",
    "            return result\n",
    "        else:\n",
    "            return []\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     #事实证明，对字符串遍历比对单词字典遍历，要快\n",
    "    \n",
    "#     def wordBreak(self, s, wordDict):\n",
    "#         \"\"\"\n",
    "#         :type s: str\n",
    "#         :type wordDict: List[str]\n",
    "#         :rtype: List[str]\n",
    "#         \"\"\"\n",
    "#         #先判断输入字符串是否为可切分\n",
    "#         wordDict = set(wordDict)\n",
    "#         length = len(s)\n",
    "#         dp = [False] * (length + 1)\n",
    "#         dp[0] = True\n",
    "#         for i in range(length):\n",
    "#             if not dp[i]:\n",
    "#                 continue\n",
    "#             for j in range(i,length):\n",
    "#                 if s[i:j + 1] in wordDict:\n",
    "#                     dp[j + 1] = True\n",
    "#             # for word in wordDict:\n",
    "#             #     if s[i : i + len(word)] == word:\n",
    "#             #         dp[i + len(word)] = True\n",
    "#         if not dp[-1]:\n",
    "#             return []\n",
    "        \n",
    "#         #在可切分的前提下，递归切分原字符串\n",
    "#         self.result = []\n",
    "#         self.helper(s,wordDict,\"\")\n",
    "#         return self.result\n",
    "    \n",
    "#     def helper(self,s,wordDict,current):\n",
    "#         #print(s)\n",
    "#         if s == \"\":\n",
    "#             self.result.append(current[:-1])\n",
    "#             #print(\"helloworld\")\n",
    "#             return\n",
    "#         # for word in wordDict:\n",
    "#         #     if word == s[:len(word)]:\n",
    "#         #         self.helper(s[len(word):],wordDict,current + word + \" \" )\n",
    "#         for i in range(len(s) + 1):\n",
    "#             word = s[:i]\n",
    "#             #print(\"s:\",s)\n",
    "#             #print(\"word:\",word)\n",
    "#             #print(\"s[i:]:\",s[i:])\n",
    "#             #print(\"\")\n",
    "#             if word in wordDict:\n",
    "#                 self.helper(s[i:],wordDict,current + word + \" \" )\n",
    "        \n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        wordDict = set(wordDict)\n",
    "        length = len(s)\n",
    "        dp = [False] * (length + 1)\n",
    "        dp[0] = True\n",
    "        for i in range(length):\n",
    "            if not dp[i]:\n",
    "                continue\n",
    "            for j in range(i,length):\n",
    "                if s[i:j + 1] in wordDict:\n",
    "                    dp[j + 1] = True\n",
    "            # for word in wordDict:\n",
    "            #     if s[i : i + len(word)] == word:\n",
    "            #         dp[i + len(word)] = True\n",
    "        if not dp[-1]:\n",
    "            return []        \n",
    "        \n",
    "        head = {0:0}\n",
    "        #head = {}\n",
    "        al = {'':[]}\n",
    "        for word in wordDict:\n",
    "            tmp = head\n",
    "            for ch in word:\n",
    "                if ch not in tmp:\n",
    "                    tmp[ch] = {0:0}\n",
    "                tmp = tmp[ch]\n",
    "            tmp[0] = 1\n",
    "        #print(head)   \n",
    "        def t(s):\n",
    "            if s in al:\n",
    "                return al[s]\n",
    "            ne = []\n",
    "            tmp = head\n",
    "            for i,ch in enumerate(s):\n",
    "                if tmp[0]:\n",
    "                    nre = t(s[i:])\n",
    "                    if nre:\n",
    "                        ne += [s[:i]+ \" \" + nr for nr in nre]\n",
    "                if ch in tmp:\n",
    "                    tmp =tmp[ch]\n",
    "                else:\n",
    "                    tmp = {0:0}\n",
    "                    break\n",
    "            if tmp[0]:\n",
    "                ne.append(s)\n",
    "            al[s] = ne\n",
    "            return ne\n",
    "\n",
    "        return t(s)        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        if not self.is_break(s, wordDict):\n",
    "            return []\n",
    "\n",
    "        dp = [[''] for _ in range(len(s) + 1)]\n",
    "\n",
    "        for i in range(1, len(s)+1):\n",
    "            words = []\n",
    "            for j in range(i):\n",
    "                if len(dp[j]) > 0 and s[j:i] in wordDict:\n",
    "                    for word in dp[j]:\n",
    "                            words.append(word + ('' if len(word) == 0 else ' ') + s[j:i])\n",
    "            dp[i] = words\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "    # 判断s是否可以被拆解成一个或多个wordDict中的单词--即139题\n",
    "    def is_break(self, s: str, wordDict: List[str]) -> bool:\n",
    "        dp = [False for _ in range(len(s) + 1)]\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(i):\n",
    "                if dp[j] and s[j:i] in wordDict:\n",
    "                    dp[i] = True\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        n = len(s)\n",
    "        if n < 1 or len(wordDict) < 1:\n",
    "            return \n",
    "        \n",
    "        wordDict = set(wordDict)\n",
    "        res = []\n",
    "\n",
    "        min_value = float(\"inf\")\n",
    "        max_value = float(\"-inf\")\n",
    "        \n",
    "        for word in wordDict:\n",
    "            min_value = min(min_value, len(word))\n",
    "            max_value = max(max_value, len(word))\n",
    "            \n",
    "        \n",
    "        dp = [False]*(n+1)\n",
    "        dp[0] = True\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if i < min_value:\n",
    "                continue\n",
    "            for j in range(max(0, i - max_value), i - min_value + 1):\n",
    "                if (dp[j]) and (s[j:i] in wordDict):\n",
    "                    dp[i] = True\n",
    "                    break      \n",
    "        if dp[n] is False:\n",
    "            return res\n",
    "         \n",
    "        def traceback(st):\n",
    "            if len(st) < 1:\n",
    "                res.append(\" \".join(tmp))\n",
    "                return \n",
    "            \n",
    "            for j in range(min_value, min(max_value+1, len(st)+1)):\n",
    "                if st[:j] in wordDict:\n",
    "                    tmp.append(st[:j])\n",
    "                    \n",
    "                    traceback(st[j:])\n",
    "                    \n",
    "                    tmp.pop()\n",
    "                    \n",
    "        tmp = []\n",
    "        traceback(s)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        memo = []\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def wordBreakBacktrack(s: str, wordDict: List[str]) -> bool:\n",
    "            if not s: \n",
    "                res.append(path[:])\n",
    "                return True\n",
    "            if len(s) in memo: return False\n",
    "            size = len(wordDict)\n",
    "            Valid = False\n",
    "            valid = False\n",
    "            for i in range(size):\n",
    "                if s.startswith(wordDict[i]):\n",
    "                    path.append(wordDict[i])\n",
    "                    valid |= wordBreakBacktrack(s[len(wordDict[i]):],wordDict)\n",
    "                    path.pop()\n",
    "                if i == size - 1 and not valid: memo.append(len(s))\n",
    "                if i == size - 1: Valid |= valid\n",
    "            return Valid\n",
    "\n",
    "        wordBreakBacktrack(s,wordDict)\n",
    "        return [' '.join(element) for element in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        flag = [False for i in range(len(s)+1)]\n",
    "        flag[0] = True\n",
    "        for i in range(1,len(s)+1):\n",
    "            for j in range(0,i):\n",
    "                if flag[j] and s[j:i] in wordDict:\n",
    "                    flag[i] = True\n",
    "        if flag[-1] == False:\n",
    "            return []\n",
    "        result = []\n",
    "        path = deque()\n",
    "        self.dfs(s,wordDict,len(s),path,result,flag)\n",
    "        # print(result)\n",
    "        return result\n",
    "    def dfs(self,s,wordDict,end,path,result,flag):\n",
    "        if s[:end] in wordDict:\n",
    "            path.appendleft(s[:end])\n",
    "            result.append(\" \".join(path))\n",
    "            # print(result)\n",
    "            path.popleft()\n",
    "        for i in range(end-1):\n",
    "            if flag[i+1] and s[i+1:end] in wordDict:\n",
    "                path.appendleft(s[i+1:end])\n",
    "                self.dfs(s,wordDict,i+1,path,result,flag)\n",
    "                path.popleft()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        \n",
    "        alphas=set()\n",
    "        for word in wordDict:\n",
    "            for alpha in word:\n",
    "                alphas.add(alpha)\n",
    "        \n",
    "        for alpha in s:\n",
    "            if alpha not in alphas:\n",
    "                return []\n",
    "\n",
    "        n=len(s)\n",
    "        canSplit=[-1]\n",
    "        strings=defaultdict(list)\n",
    "        strings[-1]=['']\n",
    "\n",
    "        for i in range(n):\n",
    "             for k in range(len(canSplit)):\n",
    "                j=canSplit[k]\n",
    "                tmpstr=s[j+1:i+1]\n",
    "                if tmpstr in wordDict:\n",
    "                    strings[i].extend([string+' '+tmpstr if string else tmpstr for string in strings[j]])\n",
    "                    if canSplit[-1]!=i:\n",
    "                        canSplit.append(i)\n",
    "        return strings[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:  \n",
    "        result = []\n",
    "        if s == \"\":\n",
    "            return result\n",
    "        wordSet = set(wordDict)\n",
    "        if len(set(\"\".join(wordSet))) < len(set(s)):\n",
    "            return result\n",
    "        \n",
    "        # use dfs\n",
    "        words = []\n",
    "        self.dfs(s, wordSet, words, result)\n",
    "        return result\n",
    "\n",
    "    def dfs(self, s, wordSet, words, result):\n",
    "        #base case\n",
    "        if s == \"\":\n",
    "            result.append(\" \".join(words))\n",
    "            return\n",
    "        else:\n",
    "            for prefix in wordSet:\n",
    "                if s[:len(prefix)] == prefix:\n",
    "                    self.dfs(s[len(prefix):], wordSet, words + [prefix], result)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        for char in s:\n",
    "            for word in wordDict:\n",
    "                if char in word:\n",
    "                    break\n",
    "            else:\n",
    "                return []\n",
    "\n",
    "        self.result = []\n",
    "        self.backtrack(s, wordDict, [])\n",
    "        return self.result\n",
    "\n",
    "    def backtrack(self, s: str, wordDict, path):\n",
    "        if s == '':\n",
    "            self.result.append(' '.join(path))\n",
    "            return\n",
    "\n",
    "        for word in wordDict:\n",
    "            if not s.startswith(word):\n",
    "                continue\n",
    "\n",
    "            path.append(word)\n",
    "            self.backtrack(s.replace(word, '', 1), wordDict, path)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        memo = [1] * (len(s)+1)\n",
    "        wordDict = set(wordDict)\n",
    "\n",
    "        def dfs(wordDict,temp,pos):\n",
    "            num = len(res)                  \n",
    "            if pos == len(s):\n",
    "                res.append(\" \".join(temp))\n",
    "                return\n",
    "            for i in range(pos,len(s)+1):\n",
    "                if memo[i] and s[pos:i] in wordDict: \n",
    "                    temp.append(s[pos:i])\n",
    "                    dfs(wordDict,temp,i)\n",
    "                    temp.pop()\n",
    "                  \n",
    "            memo[pos] = 1 if len(res) > num else 0 \n",
    "            \n",
    "        dfs(wordDict,[],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        visited = [False for _ in range(len(s)+1)]\n",
    "        wordDict = set(wordDict)\n",
    "\n",
    "        def dfs(path,pos):\n",
    "            num = len(res)                  # 回溯前先记下答案中有多少个元素\n",
    "            if pos == len(s):\n",
    "                res.append(\" \".join(path))\n",
    "                return\n",
    "            for i in range(pos,len(s)+1):\n",
    "                if not visited[i] and s[pos:i] in wordDict: # 添加备忘录的判断条件\n",
    "                    dfs(path+[s[pos:i]],i)\n",
    "            # 答案中的元素没有增加，说明s[pos:]不能分割，修改备忘录        \n",
    "            visited[pos] = False if len(res) > num else True \n",
    "            \n",
    "        dfs([],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        @lru_cache(None)\n",
    "        def backtrack(index: int) -> List[List[str]]:\n",
    "            if index == len(s):\n",
    "                return [[]]\n",
    "            ans = list()\n",
    "            for i in range(index + 1, len(s) + 1):\n",
    "                word = s[index:i]\n",
    "                if word in wordSet:\n",
    "                    nextWordBreaks = backtrack(i)\n",
    "                    for nextWordBreak in nextWordBreaks:\n",
    "                        ans.append(nextWordBreak.copy() + [word])\n",
    "            return ans\n",
    "        \n",
    "        wordSet = set(wordDict)\n",
    "        breakList = backtrack(0)\n",
    "        return [\" \".join(words[::-1]) for words in breakList]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        memo = [1] * (len(s)+1)\n",
    "        wordDict = set(wordDict)\n",
    "        @lru_cache(None)\n",
    "        def dfs(temp,pos):\n",
    "            num = len(res)                  # 回溯前先记下答案中有多少个元素\n",
    "            if pos == len(s):\n",
    "                res.append(temp.strip())\n",
    "                return\n",
    "            for i in range(pos,len(s)+1):\n",
    "                if memo[i] and s[pos:i] in wordDict: # 添加备忘录的判断条件\n",
    "                    dfs(temp+\" \"+s[pos:i],i)\n",
    "            # 答案中的元素没有增加，说明s[pos:]不能分割，修改备忘录        \n",
    "            memo[pos] = 1 if len(res) > num else 0 \n",
    "        dfs(\"\",0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        import functools\n",
    "        if not wordDict:return []\n",
    "        wordDict = set(wordDict)\n",
    "        max_len = max(map(len, wordDict)) \n",
    "        # @functools.lru_cache(None)\n",
    "        def helper(s):\n",
    "            res = []\n",
    "            if not s:\n",
    "                res.append(\"\")\n",
    "                return res\n",
    "            for i in range(len(s)):\n",
    "                if i < max_len and s[:i+1] in wordDict: \n",
    "                    for t in helper(s[i+1:]):\n",
    "                        if not t:\n",
    "                            res.append(s[:i+1])\n",
    "                        else:\n",
    "                            res.append(s[:i+1] + \" \" + t)\n",
    "            return res    \n",
    "        return helper(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        dp = [[] for i in range(len(s) + 1)]\n",
    "        dp[0] = [[]]\n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            if len(dp[i]) != 0:\n",
    "                for word in wordDict:\n",
    "                    if len(word) + i < len(dp) and word == s[i:i+len(word)]:\n",
    "                        comb = [x + [word] for x in dp[i]]\n",
    "                        dp[i+len(word)] += comb\n",
    "        return [' '.join(x) for x in dp[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        self.ans = []\n",
    "        def dfs(s, res):\n",
    "            if len(s) == 0:\n",
    "                self.ans.append(res.copy())\n",
    "            for i in range(len(s)):\n",
    "                if s[:i+1] in wordDict:\n",
    "                    res.append(s[:i+1])\n",
    "                    dfs(s[i+1:], res)\n",
    "                    res.pop()\n",
    "        dfs(s, [])\n",
    "        return [' '.join(tmp) for tmp in self.ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        MIN, MAX = float('inf'), float('-inf')\n",
    "        wordDict = set(wordDict)\n",
    "        n = len(s)\n",
    "        memo = dict()\n",
    "        for word in wordDict:\n",
    "            MIN = min(MIN, len(word))\n",
    "            MAX = max(MAX, len(word))\n",
    "        def dfs(start = 0):\n",
    "            if start == n:\n",
    "                return ['']\n",
    "            if start not in memo:\n",
    "                res = []\n",
    "                for i in range(MIN, min(MAX, n - start) + 1):\n",
    "                    if s[start : start + i] in wordDict:\n",
    "                        for substr in dfs(start + i):\n",
    "                            res.append(s[start : start + i] + ' ' + substr)\n",
    "                memo[start] = res\n",
    "            return memo[start]\n",
    "        return list(map(lambda x: x.strip(), dfs()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    # 208. 实现 Trie (前缀树) \n",
    "    # by: Broncos\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Trie)\n",
    "        self.isExist = False\n",
    "        self.isWord = False\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self  \n",
    "        for c in word:\n",
    "            cur = cur.son[c]\n",
    "            cur.isExist = True\n",
    "        cur.isWord = True\n",
    "\n",
    "    # 140题[ 单词拆分 II ] 查询写法\n",
    "    def search140(self, word: str) -> List[List[str]]:\n",
    "        n = len(word)\n",
    "        path = []\n",
    "        ans = []\n",
    "\n",
    "        def dfs(start_pos: int):\n",
    "            if start_pos == n:\n",
    "                path.pop()\n",
    "                ans.append(''.join(path))\n",
    "                path.append(' ')\n",
    "                return \n",
    "            cur = self\n",
    "            for i in range(start_pos, n):\n",
    "                cur = cur.son[word[i]]\n",
    "                if not cur.isExist: return \n",
    "                if cur.isWord:\n",
    "                    path.append(word[start_pos:i + 1])\n",
    "                    path.append(' ')\n",
    "                    dfs(i + 1)\n",
    "                    path.pop()\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for x in wordDict:\n",
    "            trie.insert(x)\n",
    "        return trie.search140(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:#不错\n",
    "    def wordBreak(self, s: str, wordDict):\n",
    "        match_dict = {}#首字母查找更快\n",
    "        for word in wordDict:\n",
    "            if word[0] not in match_dict:match_dict[word[0]] = [word]\n",
    "            else:match_dict[word[0]].append(word)\n",
    "\n",
    "        self.index_memo = {}#用这种记忆化回溯，用深度优先，这样有的就先记录下了\n",
    "        self.lenth = len(s)\n",
    "        self.ans = []\n",
    "\n",
    "        def backtrack(pointer,cur_list):\n",
    "            if pointer==self.lenth:\n",
    "                self.ans.append(' '.join(cur_list))\n",
    "            elif pointer in self.index_memo:\n",
    "                if self.index_memo[pointer]==False:\n",
    "                    return\n",
    "                else:\n",
    "                    for valid_next in self.index_memo[pointer]:\n",
    "                        self.ans.append(' '.join(cur_list+valid_next))\n",
    "            else:\n",
    "                if s[pointer] not in match_dict:\n",
    "                    self.index_memo[pointer]=False\n",
    "                else:\n",
    "                    prev_ans=self.ans.copy()\n",
    "                    for word in match_dict[s[pointer]]:\n",
    "                        if word==s[pointer:pointer+len(word)]:\n",
    "                            backtrack(pointer+len(word),cur_list+[word])\n",
    "                    new_ans=self.ans.copy()\n",
    "                    if prev_ans==new_ans:\n",
    "                        self.index_memo[pointer]=False\n",
    "                    else:\n",
    "                        upgrated_lists=new_ans[len(prev_ans):]\n",
    "                        for upgrate in upgrated_lists:\n",
    "                            upgrate=upgrate.strip().split()\n",
    "                            sub_new=upgrate[len(cur_list):]#这个点以后能串联起来的组合\n",
    "                            if pointer not in self.index_memo:\n",
    "                                self.index_memo[pointer]=[sub_new]\n",
    "                            else:\n",
    "                                self.index_memo[pointer].append(sub_new)\n",
    "\n",
    "        backtrack(0,[])\n",
    "        return self.ans\n",
    "#这种一步一步走，记忆化回溯，或者直接动态规划吧\n",
    "#两次，第一次是看连通区域。第二次是从后往前串起来（因为后面是一定可以的）\n",
    "#如果你动态规划，每一次都要和前面一个dp[i]里面存储的无数个值比较，后面会越来越大（除非dp[i]记录的是二值True，False）\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict) :\n",
    "        match_dict = {}\n",
    "        for word in wordDict:\n",
    "            if word[0] not in match_dict:\n",
    "                match_dict[word[0]] = [word]\n",
    "            else:\n",
    "                match_dict[word[0]].append(word)\n",
    "\n",
    "        lenth = len(s)\n",
    "        dp=[False for _ in range(lenth+1)]\n",
    "        dp[0]=True\n",
    "        saved=[[] for _ in range(lenth+1)]\n",
    "\n",
    "        for pointer in range(lenth):\n",
    "            if dp[pointer]==False:\n",
    "                continue\n",
    "            elif s[pointer] not in match_dict:\n",
    "                continue\n",
    "            else:\n",
    "                for candidate in match_dict[s[pointer]]:\n",
    "                    if candidate==s[pointer:pointer+len(candidate)]:\n",
    "                        dp[pointer+len(candidate)]=True\n",
    "                        saved[pointer+len(candidate)].append(candidate)\n",
    "\n",
    "        if dp[-1]==False:\n",
    "            return []\n",
    "\n",
    "        self.ans=[]\n",
    "        def backtack(pointer,cur_list):\n",
    "            if pointer==0:\n",
    "                self.ans.append(cur_list)\n",
    "            else:\n",
    "                for candidate in saved[pointer]:\n",
    "                    if pointer==lenth:\n",
    "                        backtack(pointer-len(candidate),candidate)\n",
    "                    else:\n",
    "                        backtack(pointer-len(candidate),candidate+' '+cur_list)\n",
    "        backtack(lenth,'')\n",
    "        return self.ans\n",
    "\n",
    "'''\n",
    "#放进队列中会超时，因为我用的是宽度优先，没有记忆化回溯\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict):\n",
    "        match_dict=defaultdict(list)\n",
    "        for word in wordDict:\n",
    "            match_dict[word[0]].append(word)#提前建好桶，以便在字典里查找，避免每次遍历\n",
    "\n",
    "        #BFS,DFS\n",
    "        self.memo=deque()\n",
    "        lenth=len(s)\n",
    "        if s[0] not in match_dict:return []\n",
    "        else:\n",
    "            for candidate in match_dict[s[0]]:\n",
    "                len_candidate=len(candidate)\n",
    "                if s[:len_candidate]==candidate:\n",
    "                    self.memo.append((len_candidate,[candidate]))\n",
    "\n",
    "        self.ans=[]\n",
    "        while self.memo:\n",
    "            cur_ptr,visited=self.memo.popleft()\n",
    "            if cur_ptr==lenth:\n",
    "                self.ans.append(' '.join(visited))\n",
    "            elif cur_ptr<lenth:\n",
    "                if s[cur_ptr] in match_dict:\n",
    "                    for candidate in match_dict[s[cur_ptr]]:\n",
    "                        len_candidate = len(candidate)\n",
    "                        if s[cur_ptr:cur_ptr+len_candidate]==candidate:\n",
    "                            self.memo.append((cur_ptr+len_candidate,visited+[candidate]))\n",
    "\n",
    "        return self.ans\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        match_dict = {}\n",
    "        for word in wordDict:\n",
    "            if word[0] not in match_dict:match_dict[word[0]] = [word]\n",
    "            else:match_dict[word[0]].append(word)\n",
    "\n",
    "        from collections import deque\n",
    "        memo=deque()\n",
    "        memo.append((0,[]))\n",
    "        self.ans=[]\n",
    "        while memo:\n",
    "            cur_ptr,saved=memo.popleft()\n",
    "            if cur_ptr==len(s):\n",
    "                self.ans.append(' '.join(saved))\n",
    "            else:\n",
    "                if s[cur_ptr] in match_dict:\n",
    "                    for candidate_word in match_dict[s[cur_ptr]]:\n",
    "                        if len(candidate_word)+cur_ptr<=len(s) and s[cur_ptr:cur_ptr+len(candidate_word)]==candidate_word:\n",
    "                            memo.append((cur_ptr+len(candidate_word),saved+[candidate_word]))\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict) -> bool:\n",
    "        queue=deque()\n",
    "        queue.append((s,[]))\n",
    "        self.ans=[]\n",
    "        while queue:\n",
    "            left_match,history=queue.pop()\n",
    "            for word in wordDict:\n",
    "                if word==left_match[:len(word)]:\n",
    "                    if left_match[len(word):]==\"\":\n",
    "                        self.ans.append(\" \".join(list(map(str,history+[word]))))\n",
    "                    else:\n",
    "                        queue.append((left_match[len(word):],history+[word]))\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        # 将单词字典转换为集合，以便快速判断一个单词是否在字典中\n",
    "        wordSet = set(wordDict)\n",
    "        # 使用字典来保存已经计算过的子问题的结果，避免重复计算\n",
    "        memo = {}\n",
    "\n",
    "        def backtrack(s):\n",
    "            # 如果已经计算过当前子问题的结果，则直接返回\n",
    "            if s in memo:\n",
    "                return memo[s]\n",
    "\n",
    "            # 如果字符串s为空，则返回一个空列表作为结果\n",
    "            if not s:\n",
    "                return []\n",
    "\n",
    "            # 用于保存当前子问题的结果\n",
    "            res = []\n",
    "\n",
    "            # 遍历字符串s的所有前缀\n",
    "            for i in range(1, len(s) + 1):\n",
    "                prefix = s[:i]\n",
    "\n",
    "                # 如果前缀在单词字典中，则递归计算剩余部分的结果\n",
    "                if prefix in wordSet:\n",
    "                    # 如果剩余部分为空，则将前缀作为一个结果加入列表\n",
    "                    if i == len(s):\n",
    "                        res.append(prefix)\n",
    "                    else:\n",
    "                        # 递归计算剩余部分的结果\n",
    "                        suffixes = backtrack(s[i:])\n",
    "\n",
    "                        # 将前缀和剩余部分的结果组合起来\n",
    "                        for suffix in suffixes:\n",
    "                            res.append(prefix + \" \" + suffix)\n",
    "\n",
    "            # 将当前子问题的结果保存到字典中\n",
    "            memo[s] = res\n",
    "            return res\n",
    "\n",
    "        # 调用回溯函数，得到最终结果\n",
    "        return backtrack(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        '''\n",
    "        回溯法列出所有方案\n",
    "        '''\n",
    "        res = []\n",
    "        self.backtrack(s, wordDict, res, ' ')\n",
    "        return res\n",
    "    \n",
    "    def backtrack(self, s, wordDict, res, path):\n",
    "        if not s:\n",
    "            res.append(path[1:-1])\n",
    "            return res\n",
    "        prev = ''\n",
    "        for i, c in enumerate(s):\n",
    "            prev += c\n",
    "            if prev in wordDict:\n",
    "                self.backtrack(s[i+1:], wordDict, res, path + prev + ' ')  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        max_length=10\n",
    "        s_length=len(s)\n",
    "        word_set=set(wordDict)\n",
    "        result=[]\n",
    "\n",
    "\n",
    "        def dfs(pre_word:list,start_ids:int):\n",
    "            if start_ids>=s_length:\n",
    "                result.append(' '.join(pre_word))\n",
    "                return\n",
    "\n",
    "            for i in range(start_ids+1,min(start_ids+max_length,s_length)+1):\n",
    "                next_word=s[start_ids:i]\n",
    "                if next_word in word_set:\n",
    "                    pre_word.append(next_word)\n",
    "                    dfs(pre_word,i)\n",
    "                    pre_word.pop()\n",
    "        \n",
    "        dfs([],0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        l = len(s)\n",
    "        dp = [False for c in s]\n",
    "        for i in range(len(s)):\n",
    "            for word in wordDict:\n",
    "                k = len(word)\n",
    "                if i+1 >= k:\n",
    "                    if s[i-k+1:i+1] == word:\n",
    "                        if i==k-1 or dp[i-k]:\n",
    "                            dp[i] = True\n",
    "                            break\n",
    "        return dp[-1]\n",
    "        \n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':\n",
    "        ns = len(s)\n",
    "        memo = [False for i in range(ns)]\n",
    "        for i in range(ns - 1, -1, -1):\n",
    "            for word in wordDict:\n",
    "                if i + len(word) == ns:\n",
    "                    memo[i] |= (s[i:] == word)\n",
    "                elif i + len(word) < ns:\n",
    "                    memo[i] |= (s[i:i+len(word)] == word) and memo[i + len(word)]\n",
    "        # print(memo)\n",
    "        return memo[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(s)        \n",
    "        f = [False] * (n+1)\n",
    "        f[0] = True\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if f[j] and s[j:i] in wordDict:\n",
    "                    f[i] = True\n",
    "                    break\n",
    "        return f[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':\n",
    "        lg = len(s)\n",
    "        words = set(wordDict)\n",
    "        dp = dict()\n",
    "\n",
    "        def func(k):\n",
    "            res = dp.get(k, None)\n",
    "            if res is not None:\n",
    "                return res\n",
    "\n",
    "            if k == lg:\n",
    "                dp[k] = True\n",
    "                return True\n",
    "\n",
    "            for i in range(k+1, lg+1):\n",
    "                if s[k:i] in words:\n",
    "                    if func(i):\n",
    "                        dp[k] = True\n",
    "                        return True\n",
    "            dp[k] = False\n",
    "            return False\n",
    "\n",
    "        return func(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return True\n",
    "        if not wordDict:\n",
    "            return False\n",
    "        wordDict_Set = set(wordDict)\n",
    "        check_list = [False for _ in range(len(s)+1)]\n",
    "        check_list[0] = True\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(len(wordDict)):\n",
    "                if i >= len(wordDict[j]):\n",
    "                    if s[i-len(wordDict[j]):i] in wordDict_Set and check_list[i-len(wordDict[j])]== True:\n",
    "                        print(s[i-len(wordDict[j]): i])\n",
    "                        check_list[i] = True\n",
    "\n",
    "        print(check_list)\n",
    "        return check_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        mark = [0]*(len(s)+1)\n",
    "        mark[0] = 1\n",
    "        for i in range(1,len(s)+1):\n",
    "            for j in range(i):\n",
    "                if mark[j] and s[j:i] in wordDict:\n",
    "                    mark[i] = 1\n",
    "                    break\n",
    "        if mark[len(s)] == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        wordDict=set(wordDict)\n",
    "        dp = [False for i in range(n+1)]\n",
    "        dp[0]=True\n",
    "        for i in range(1,n+1):\n",
    "            for word in wordDict:\n",
    "                l=len(word)\n",
    "                if i>=l and not dp[i]:\n",
    "                    print (i)\n",
    "                    dp[i]=(dp[i-l]) and (s[i-l:i] in wordDict)\n",
    "        print (dp)\n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #前缀树解决\n",
    "        #建立树\n",
    "        trie=Trie()\n",
    "        for word in wordDict:\n",
    "            trie.add(word)\n",
    "        sub=[1]+[0]*len(s)\n",
    "        for i in range(len(s)+1):\n",
    "            if sub[i]==0:continue\n",
    "            for t in trie.search(s[i:]):\n",
    "                sub[i+1+t]=1\n",
    "        return sub[-1]==1\n",
    "from collections import defaultdict\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.dic=defaultdict(TrieNode)\n",
    "        self.isend=False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root=TrieNode()\n",
    "    def add(self,st):\n",
    "        temp=self.root\n",
    "        for c in st:\n",
    "            if c not in temp.dic:\n",
    "                temp.dic[c]=TrieNode()\n",
    "            temp=temp.dic[c]\n",
    "        temp.isend=True\n",
    "    #找能对应到前缀的坐标\n",
    "    def search(self,si):\n",
    "        re=[]\n",
    "        temp=self.root\n",
    "        for i in range(len(si)):\n",
    "            if si[i] in temp.dic:\n",
    "                temp=temp.dic[si[i]]\n",
    "                if temp.isend:re.append(i)\n",
    "            else:\n",
    "                return re\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.dict = {}\n",
    "        return self.dfs(s, wordDict)\n",
    "\n",
    "    def dfs(self, s, wordDict):\n",
    "        # print(wordDict)\n",
    "        if (len(s) == 0 or s in wordDict):\n",
    "            return True\n",
    "        for i in range(len(s)):\n",
    "            if not i == 0 :\n",
    "                left = s[:i]\n",
    "                right = s[i:]\n",
    "                if not (left in self.dict.keys()):\n",
    "                    left_flag = self.dfs(left,wordDict)\n",
    "                    self.dict[left] = left_flag\n",
    "                if not (right in self.dict.keys()):\n",
    "                    right_flag = self.dfs(right,wordDict)\n",
    "                    self.dict[right] = right_flag\n",
    "                \n",
    "                \n",
    "                if(self.dict[left] and self.dict[right]):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=139 lang=python3\n",
    "#\n",
    "# [139] 单词拆分\n",
    "#\n",
    "# https://leetcode-cn.com/problems/word-break/description/\n",
    "#\n",
    "# algorithms\n",
    "# Medium (38.13%)\n",
    "# Total Accepted:    4K\n",
    "# Total Submissions: 10.6K\n",
    "# Testcase Example:  '\"leetcode\"\\n[\"leet\",\"code\"]'\n",
    "#\n",
    "# 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。\n",
    "# \n",
    "# 说明：\n",
    "# \n",
    "# \n",
    "# 拆分时可以重复使用字典中的单词。\n",
    "# 你可以假设字典中没有重复的单词。\n",
    "# \n",
    "# \n",
    "# 示例 1：\n",
    "# \n",
    "# 输入: s = \"leetcode\", wordDict = [\"leet\", \"code\"]\n",
    "# 输出: true\n",
    "# 解释: 返回 true 因为 \"leetcode\" 可以被拆分成 \"leet code\"。\n",
    "# \n",
    "# \n",
    "# 示例 2：\n",
    "# \n",
    "# 输入: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]\n",
    "# 输出: true\n",
    "# 解释: 返回 true 因为 \"applepenapple\" 可以被拆分成 \"apple pen apple\"。\n",
    "# 注意你可以重复使用字典中的单词。\n",
    "# \n",
    "# \n",
    "# 示例 3：\n",
    "# \n",
    "# 输入: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]\n",
    "# 输出: false\n",
    "# \n",
    "# \n",
    "#\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':\n",
    "        wordDict = set(wordDict)\n",
    "        @lru_cache(None)\n",
    "        def  _wordBreak(x):\n",
    "            if x in wordDict:\n",
    "                return True\n",
    "            for i in range(len(x)):\n",
    "                if _wordBreak(x[:i]) and _wordBreak(x[i:]):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return _wordBreak(s)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    print(s.wordBreak('leetcode', ['leet', 'code']))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        '''\n",
    "        #set先排除特殊情况，依然超时\n",
    "        set1 = set(s)\n",
    "        dicts = \"\"\n",
    "        for word in wordDict:\n",
    "            dicts +=word\n",
    "        set2 = set(dicts)\n",
    "        if not set1.issubset(set2):\n",
    "            return False\n",
    "        '''\n",
    "        '''\n",
    "        if not s:\n",
    "            return True\n",
    "        #wordDict.sort(key=len,reverse=True)  #先长的字符串匹配，依然超时\n",
    "        for word in wordDict:\n",
    "            if s.startswith(word):\n",
    "                n = len(word)\n",
    "                if self.wordBreak(s[n:],wordDict):\n",
    "                    return True\n",
    "        return False\n",
    "        '''\n",
    "        n = len(s)\n",
    "        dp = [False] *(n+1)\n",
    "        dp[0]= True\n",
    "        wordDict = set(wordDict)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if dp[j] and (s[j:i] in wordDict):\n",
    "                    dp[i] =True\n",
    "                    break \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n=len(s)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if dp[i] and s[i:j] in wordDict:\n",
    "                    dp[j]=True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i]：s[:i]是否能拆成wordDict\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        dp = [0]*(len(s)+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, len(s)+1):\n",
    "            # 因为单词顺序不固定且无限，故物品应在内层正序迭代\n",
    "            for word in wordDict:\n",
    "                n = len(word)\n",
    "                if i>=n and word == s[i-n:i]:\n",
    "                    dp[i] = dp[i] or dp[i-n]\n",
    "        print(dp)\n",
    "        return dp[len(s)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n=len(s)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if(dp[i] and (s[i:j] in wordDict)):\n",
    "                    dp[j]=True\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        length = len(s)\n",
    "        dp = [False]*(length+1)\n",
    "        dp[0] = True\n",
    "        for i in range(length):\n",
    "            for j in range(i+1,length+1):\n",
    "                if (dp[i] and (s[i:j] in wordDict)):\n",
    "                    dp[j] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [False] * (n+1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if (dp[i] and s[i:j] in wordDict):\n",
    "                    dp[j] = True\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        dp = [False] * (len(s) + 1)\n",
    "        n = len(s)\n",
    "        dp[0] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n+1):\n",
    "                if dp[i] and s[i:j] in wordDict:\n",
    "                    dp[j] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [False for _ in range(n + 1)]\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                suffix = s[j:i]\n",
    "                if suffix in wordDict and dp[j]:\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def back_track(s):\n",
    "            if (not s):\n",
    "                return True\n",
    "            res = False\n",
    "            for i in range(1, len(s) + 1):\n",
    "                if (s[:i] in wordDict):\n",
    "                    res = back_track(s[i:]) or res\n",
    "            return res\n",
    "        return back_track(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def back_track(s):\n",
    "            if not s:\n",
    "                return True\n",
    "            res = False\n",
    "            for i in range(1, len(s) + 1):\n",
    "                if s[:i] in wordDict:\n",
    "                    res = back_track(s[i:]) or res\n",
    "            return res\n",
    "        return back_track(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        P = 131\n",
    "        mapping = defaultdict(int)\n",
    "        dp = [False] * (len(s) + 1)\n",
    "        dp[0] = True\n",
    "        for each in wordDict:\n",
    "            tmp = 0\n",
    "            for ch in each:\n",
    "                tmp = (tmp * P + ord(ch)) % (1 << 64)\n",
    "            mapping[tmp] = 1\n",
    "        for i in range(len(s) + 1):\n",
    "            if dp[i]:\n",
    "                tmp = 0\n",
    "                for j in range(i + 1, len(s) + 1):\n",
    "                    tmp = (tmp * P + ord(s[j - 1])) % (1 << 64)\n",
    "                    if mapping[tmp]:\n",
    "                        dp[j] = True\n",
    "        return dp[len(s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        \n",
    "        def insert(word):\n",
    "            node = self.root\n",
    "            for ch in word:\n",
    "                if node.__contains__(ch):\n",
    "                    node = node[ch]\n",
    "                else:\n",
    "                    node[ch] = {}\n",
    "                    node = node[ch]\n",
    "            node['is_end'] = True\n",
    "\n",
    "        def search(node,word):\n",
    "            for ind in range(len(word)):\n",
    "                ch = word[ind]\n",
    "                if node.__contains__(ch):\n",
    "                    node = node[ch]\n",
    "                else:\n",
    "                    return False\n",
    "            if node.__contains__('is_end'):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for word in wordDict:\n",
    "            insert(word)\n",
    "\n",
    "        length = len(s)\n",
    "        dp = [False]*(length+1)\n",
    "        dp[0] = True\n",
    "        for i in range(1,length+1):\n",
    "            for j in range(i):\n",
    "                if dp[j] and search(self.root,s[j:i]):\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "        return dp[length]\n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        # 动态规划：元素个数可重复添加——>完全背包；且组成字符串s的单词与顺序有关，应该归为求排列\n",
    "        # 求排列：先背包，后物品\n",
    "        # 确定dp含义：dp[i]：表示字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。\n",
    "        # 其实解法类似 377. 组合总和 Ⅳ\n",
    "        dp = [False]*(len(s)+1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(len(s)+1):# 遍历背包\n",
    "            for j in wordDict: # 遍历物品\n",
    "                if i >= len(j):\n",
    "                    # 前者：长度为i的字符串不能再放单词j,后者为可再放单词j进行\n",
    "                    dp[i] = dp[i] or (dp[i - len(j)] and j == s[i - len(j):i])  # 递归\n",
    "        return dp[len(s)]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n=len(s)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(1,n+1):\n",
    "            for word in wordDict:\n",
    "                if s[:i].endswith(word) and dp[i-len(word)]:\n",
    "                    dp[i]=True\n",
    "                    break\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [False] * (n + 1)\n",
    "        dp[0] = True\n",
    "        for i in range(1, n + 1):\n",
    "            for word in wordDict:\n",
    "                wordLen = len(word)\n",
    "                if i >= wordLen and s[i-wordLen: i] == word:\n",
    "                    dp[i] = dp[i-wordLen] or dp[i]\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        dp = [False]*(len(s)+1)\n",
    "        dp[0] = True\n",
    "        for i in range(len(s)+1):\n",
    "            for word in wordDict:\n",
    "                if i>=len(word) and dp[i - len(word)] and word == s[i-len(word):i]:\n",
    "                    dp[i] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        # 拼接出 s \n",
    "        #\n",
    "        # n = len(s)\n",
    "        # dp = [False] * (n + 1)\n",
    "        # dp[0] = True\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1,n + 1):\n",
    "        #         if (dp[i] and (s[i:j] in wordDict)):\n",
    "        #             dp[j] = True\n",
    "        # return dp[-1]\n",
    "        import functools\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def back_track(s):\n",
    "            if not s:\n",
    "                return True\n",
    "            res = False\n",
    "            for i in range(1,len(s) + 1):\n",
    "                if s[:i] in wordDict:\n",
    "                    res = back_track(s[i:]) or res\n",
    "            return res\n",
    "        return back_track(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [False]*(n+1)\n",
    "        dp[0] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if dp[i] and s[i:j] in wordDict:\n",
    "                    dp[j] = True\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [False]*(n+1)\n",
    "        dp[0] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n+1):\n",
    "                if dp[i] and s[i:j] in wordDict:\n",
    "                    dp[j] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        st = set(wordDict)\n",
    "        n = len(s)\n",
    "        dp = [True] + [False] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if dp[i] and (s[i:j] in st):\n",
    "                    dp[j] = True\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        # 我的做法甚至能给出排列数。可以通过注释中的测试样例判断。这个样例有 >1 种方法\n",
    "        # 输出方法数就是 return dp[len(s)]\n",
    "        # s = \"abcabcabbcca\"\n",
    "        # wordDict = [\"a\", \"b\", \"c\", \"ab\", \"bc\", \"ca\"]\n",
    "        dp = [0 for i in range(len(s) + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(0, len(s) + 1):\n",
    "            for word in wordDict:\n",
    "                if j >= len(word) and s[j - len(word) : j] == word:\n",
    "                    dp[j] += dp[j - len(word)]\n",
    "        if dp[len(s)] != 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
